﻿#define _CRT_SECURE_NO_WARNINGS 1
//排序数组: https://leetcode.cn/problems/sort-an-array/
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        srand(time(NULL)); // 种下⼀个随机数种⼦
        qsort(nums, 0, n - 1);
        return nums;
    }
    void qsort(vector<int>& nums, int begin, int end)
    {
        if (begin > end) return;

        int mid = getRandom(nums, begin, end);  //随机数
        int n = begin - end + 1;
        int left = begin - 1, i = begin, right = end + 1;
        while (i < right)
        {
            if (nums[i] == mid)
            {
                i++;
            }
            else if (nums[i] < mid)
            {
                swap(nums[i++], nums[++left]);
            }
            else
            {
                swap(nums[--right], nums[i]);
            }
        }
        //[begin,left] [right,end]
        qsort(nums, begin, left);
        qsort(nums, right, end);
    }
    int getRandom(vector<int>& nums, int begin, int end)
    {
        int r = rand();
        int i = r % (end - begin + 1) + begin;
        return nums[i];
    }
};